COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M0NGR30\M1BASI30\M2BASB30\F0
C00015 ENDMK
C⊗;
\\M0NGR30;\M1BASI30;\M2BASB30;\F0

WHAT IS A PATTERN?


\J	In many areas of programming and especially in artificial
intelligence, it is effective to create and use patterns.  The use
involves recognizing the pattern in a situation and taking
an appropriate action.  More generally, the action taken may depend
on a set of patterns and other information as well.

	The most well developed forms of pattern and pattern
recognition occur in formal syntax of languages where the
languages are strings of symbols.  I want to define patterns
abstractly quite separately from language but hopefully in a way
that is applicable to language and in a way that will enable
some of the properties of linguistic patterns that have been
studied to carry over to \F1abstract patterns\F0.

	When I have tried to give a fully general definition of
pattern, the ideas have gotten quite complex and no \F1most general\F0
idea has come out.  Therefore, I will try to sneak up on it
and start with the simplest kinds of patterns.


Type I patterns

	A type I pattern is specified by giving a collection
of predicates and a quantifier free expression in these
predicate symbols.  An instance of the pattern is a pairing of
entities with the free individual variables such that when
the variables are assigned the corresponding entities, the
expression is true.

	The notion of pin in chess can be given as
an example of a type I pattern provided it is described in
terms of the following predicates:

	1. iswhite(piece) asserts that \F1piece\F0 is white.

	2. sees(piece1,piece2,direction,board) asserts that
if one moves from \F1piece1\F0 in the direction \F1direction\F0
on the board situation \F1board\F0, one encounters \F1piece\F0
before encountering a non-blank square or the edge of the
board.

	2. moves(piece,direction) asserts that \F1piece\F0
moves an arbitrary distance, (it therefore must be a
queen, rook, or bishop) in \F1direction\F0.

	3. better(piece1,piece2) asserts that \F1piece1\F0
has a higher value than \F1piece2\F0.

	4. defended(piece,board) asserts that \F1piece\F0 is
defended in the position \F1board\F0.

	Pins are then described by a formula involving five
free variables, namely \F1piece1\F0 - the pinning piece,
\F1piece2\F0 - the pinned piece, \F1piece3\F0 - the piece
against which \F1piece2\F0 is pinned, \F1direction\F0 -
the direction from \F1piece1\F0 to \F1piece2\F0, and 
\F1board\F0 - the board position in which all this occurs.  The formula
is
	\F1iswhite(piece1) ≡ iswhite(piece3) ∧
	iswhite(piece1) ≡ ¬iswhite(piece2) ∧
	sees(piece1,piece2,direction,board) ∧
	sees(piece2,piece3,direction,board) ∧
	moves(piece1,direction) ∧
	[¬defended(piece3,board) ∨ better(piece3,piece1)].\F0

	This simple example suggests the following remarks:

	1. The simplest linguistic patterns are of type I.
These give a special role to the relation

	\F1ispredecessor(string1,string2,string3)\F0

which asserts that \F1string1\F0 immediately precedes
\F1string2\F0 in their occurence as substrings of \F1string3\F0.

Thus strings consisting of noun phrases followed by verb phrases
which give one form of sentence in some simple grammars are
examples of the pattern\F1

	ispredecessor(string1,string2,string3) ∧
	nounphrase(string1) ∧
	verbphrase(string2).\F0

	2. Since a substantial part of the generalization we are
looking for consists merely in not giving a special role to the
relation \F1ispredecessor\F0, it is likely that some of the
interesting properties of string patterns carry over to the
general case.

	3. Given the small number of pieces in a chess position,
it is clearly feasible to find pins in a position given
programs for calculating the predicates involved.  This involves
specifying one of the elements of the pattern, namely \F1board\F0
which thereby plays a special role and scanning the others.
An ad hoc pin recognizer is clearly easy to write, and it
is even easy to write a general pattern recognizer for patterns
involving a single board variable, several piece variables, and
several direction variables.
However, a recognizer that had to scan all possible positions
is infeasible and not wanted for chess play anyway.  Moreover,
the different roles played by pieces and directions (e.g. it
if we scan the potential pinning pieces and the directions
leading from them first, we need only look for potential
pinned pieces in the given direction), makes it unlikely that
the techniques of grammatical pattern recognition have much
carryover to the general case.

	4. One is tempted to use existing patterns in
defining new patterns, and in order to do this, we need to
allow binding some variables with existential quantifiers.
Thus we obviously want to define

	pinned(piece,board) ≡ ∃ piece1 piece3 direction.
		pins(piece1,piece,piece3,direction,board),

and the predicate \F1defended\F0 used in the definition of
\F1pins\F0 obviously wants to be defined in terms of a pattern.

	In the study of grammatical patterns, the highly recursive
cases are emphasized, because they are necessary for any kind
of generality, because Chomsky fascinated the linguists
with the competence-performance distinction, and because
they are mathematically the most interesting.  Nevertheless,
non-recursive patterns occur in many practical cases and probably usually
admit simpler methods of recognition and use.
Therefore we shall take type I patterns to be non-recursive,
and reserve recursion for a later type.

	5. In one respect, type I patterns go beyond context free
phrase structure grammars in the string case.  Namely, the
same variable can occur in several places in the defining
expression, and this allows the imposition of requirements
of agreement from the beginning.  I doubt that the requirement
that all occurences of variables be of different variables
leads to an interesting class of patterns.  Moreover, it
doesn't give the context free patterns in the grammar case
unless we distinguish the \F1ispredecessor\F0 function,
because a variable has to occur in the \F1ispredecessor\F0
relation and also in the other predicates.  This simply
confirms my prejudice against context freedom.

	6. In writing the \F1pin\F0 pattern, it was
an inconvenience not to be able to use the function
\F1color(piece)\F0, but we got around it with the
predicate \F1iswhite\F0 at the cost of awkwardness.
It would seem that any pattern that can be written
with functions can also be written using only the
corresponding predicates provided we use existential
quantifiers to get rid of unwanted variables that have to
be introduced.  Thus the relation\F1

	y = f(g(h(x)))\F0

which might occur in some pattern would have to be
replaced by

\F1     F(y,u) ∧ G(u,v) ∧ H(v,x)   \F0

where \F1f\F0 and \F1F\F0 are related by

\F1     ∀ x y.(y = f(x) ≡ F(y,x)).    \F0

Thus we would get a pattern with more variables, and the
extras can be eliminated with existential quantifiers.
Suppose we call the patterns we get allowing function
symbols type I-a.  It is an open question whether we should
do this or whether we should admit the function symbols
directly into type I.

	6. We shall not try to define more types of patterns
in this draft.  However, note the following directions of
generalization:

		a. The computation of the predicate expression
could involve more complicated calculations such as recursion.
Thus a pin is not a type I pattern if we can't use
\F1sees(piece1,piece2,direction,board)\F0, but have to build
it from the relation \F1adjacent(square1,square2,direction)\F0.

		b. Variable numbers of entities may appear in
patterns.

		c. The conditions for one pattern may require
the non-existence of other patterns.

	7. The example of pinning shows that patterns may be
used in much more varied ways than in linguistics whether of
natural or computer languages.  Some typology of the ways
in which patterns are used after being recognized is probably
worthwhile.\.